Hard
Related Topics: Hash Table / String / Greedy / Sorting / Counting
LeetCode Source

解題想法

我們建立 mapping 的 hash table

用來映射當前數值到英文字串

而我們依照 billion, million, thousand 和餘數來更新字串表示

而在更細步，我們藉由百位數、十位數、十幾位數、個位數設置相對映的 function

Complexity

Time Complexity: O(logn)
Space Complexity: O(logn)

Python

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"

        d = {0: "Zero",
            1: "One",
            2: "Two",
            3: "Three",
            4: "Four",
            5: "Five",
            6: "Six",
            7: "Seven",
            8: "Eight",
            9: "Nine",
            10: "Ten",
            11: "Eleven",
            12: "Twelve",
            13: "Thirteen",
            14: "Fourteen",
            15: "Fifteen",
            16: "Sixteen",
            17: "Seventeen",
            18: "Eighteen",
            19: "Nineteen",
            20: "Twenty",
            30: "Thirty",
            40: "Forty",
            50: "Fifty",
            60: "Sixty",
            70: "Seventy",
            80: "Eighty",
            90: "Ninety",
        }

        def one(num):
            return d[num]

        def two_less_20(num):
            return d[num]

        def ten(num):
            return d[num]

        def two(num):
            if not num:
                return ""
            elif num < 20:
                return two_less_20(num)
            else:
                tenner = num // 10 * 10
                rest = num % 10
                return ten(tenner) + " " + one(rest) if rest else ten(tenner)

        def three(num):
            hundred = num // 100
            rest = num % 100
            if hundred and rest:
                return one(hundred) + " Hundred " + two(rest)
            elif not hundred and rest:
                return two(rest)
            elif hundred and not rest:
                return one(hundred) + " Hundred"

        billion = num // 1000000000
        million = (num % 1000000000) // 1000000
        thousand = (num % 1000000) // 1000
        remainder = num % 1000

        result = ""
        if billion:
            result += three(billion) + " Billion"
        if million:
            result += " " if result else ""
            result += three(million) + " Million"
        if thousand:
            result += " " if result else ""
            result += three(thousand) + " Thousand"
        if remainder:
            result += " " if result else ""
            result += three(remainder)

        return result

C++

class Solution {
public:
    std::string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }

        std::vector<std::string> below_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
                                             "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        std::vector<std::string> below_100 = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        std::vector<std::string> thousands = {"", "Thousand", "Million", "Billion"};

        std::string result;
        int thousandCounter = 0;

        while (num > 0) {
            if (num % 1000 != 0) {
                result = helper(num % 1000, below_20, below_100) + thousands[thousandCounter] + " " + result;
            }
            num /= 1000;
            thousandCounter++;
        }

        while (result.back() == ' ') {
            result.pop_back();
        }

        return result;
    }

private:
    std::string helper(int num, const std::vector<std::string>& below_20, const std::vector<std::string>& below_100) {
        if (num == 0) {
            return "";
        } else if (num < 20) {
            return below_20[num] + " ";
        } else if (num < 100) {
            return below_100[num / 10] + " " + helper(num % 10, below_20, below_100);
        } else {
            return below_20[num / 100] + " Hundred " + helper(num % 100, below_20, below_100);
        }
    }
};